package problem518;

//518.零钱兑换2
//https://leetcode.cn/problems/coin-change-ii/description/

// class Solution {
//     public int change(int m, int[] coins) {
//         int n = coins.length;
//         int[][] dp = new int[n+1][m+1];
//         dp[0][0] = 1;
//         for(int i = 1; i<=n; i++) {
//             for(int j = 0; j<=m; j++) {
//                 dp[i][j] += dp[i-1][j];
//                 if(j-coins[i-1] >= 0) dp[i][j] += dp[i][j-coins[i-1]];
//             }
//         }
//         return dp[n][m];
//     }
// }

/*

dp[i][j]:从前 i 中物品中选, 能组成面值为 j 得种数
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]] + dp[i][j-2*coins[i]] + dp[i][j-3*coins[i]] + ... + dp[i][j-k*coins[i]]
dp[i][j-coins[i]] =      dp[i-1][j-coins[i]] + dp[i][j-2*coins[i]] + ... + dp[i][j-k*coins[i]];
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]];

*/

class Solution {
    public int change(int m, int[] coins) {
        int n = coins.length;
        int[] dp = new int[m+1];
        dp[0] = 1;
        for(int i = 1; i<=n; i++) {
            for(int j = coins[i-1]; j<=m; j++) {
                dp[j] += dp[j-coins[i-1]];
            }
        }
        return dp[m];
    }
}